package paint_house;

/**
 * 有一排N栋房子，每栋房子都可以涂上其中一种K颜色。
 * 用某种颜色粉刷每栋房子的费用是不同的。
 * 你必须把所有的房子都漆成没有两个相邻的房子有相同的颜色。
 *
 * 用一个n x k的成本矩阵表示每栋房子涂上某种颜色的成本。
 * 例如，costs[0][0]是用颜色0绘制房子0的成本；
 * costs[1][2]是用颜色2绘制房子1的成本，等等…
 * 找出油漆所有房屋的最低成本。
 *
 * 遍历每个房子的cost,如果与前一个最小位置冲突，+前一个的次小cost,否则+前一个的最小cost
 * @create: 2021-05-04 14:49
 **/
public class Paint265 {
    public static void main(String[] args) {
        int[][] costs=new int[][]{
                {12,3,4,6},
                {2,1,4,3},
                {3,4,2,1}
        };
        int minCost = minCostII(costs);
        System.out.println("minCost = " + minCost);
    }
    public static int minCostII(int[][] costs){
//        记录前一个房子的最小金额，次小金额
        int preMin=0,preSec=0,preIndex=-1;
        for(int i=0;i<costs.length;i++){
//            当前房子的最小金额，次小金额，最后赋值给前一个
//            curIndex最小的索引
            int curMin=Integer.MAX_VALUE,curSec=Integer.MAX_VALUE,curIndex=-1;
            for(int j=0;j<costs[0].length;j++){
//                当前房子颜色与上一次颜色相同，取次小
                if(preIndex==j){
                    costs[i][j]=costs[i][j]+preSec;
                }else {
                    costs[i][j]=costs[i][j]+preMin;
                }
//                获取最小值
                if(costs[i][j]<curMin){
                    curSec=curMin;
                    curMin=costs[i][j];
                    curIndex=j;
                }else if(costs[i][j]<curSec){
                    curSec=costs[i][j];
                }
            }
//            赋值前一个
            preMin=curMin;
            preSec=curSec;
            preIndex=curIndex;
        }
        return preMin;
    }
}
